package leetcode.editor.cn.dsa11_sort;
// 按奇偶排序数组 II

import java.util.Arrays;

public class SortArrayByParityIi922_1 {
    public static void main(String[] args) {
        Solution solution = new SortArrayByParityIi922_1().new Solution();
        int[] arr = {4,2,5,7};
        solution.sortArrayByParityII(arr);
        System.out.println(Arrays.toString(arr));
        int[] arr2 = {1,2,3,4,5,6,7,8};
        solution.sortArrayByParityII(arr2);
        System.out.println(Arrays.toString(arr2));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] sortArrayByParityII(int[] A) {
            /**
             * 最优解：
             * 1.使用位运算判断奇偶数，如果是奇数，二进制的末位一定是1，偶数则一定是0
             * 2.题目规定A中一半整数是奇数，一半整数是偶数，因此循环中判断一个索引位是否越界即可
             *   由于我们判断中以偶数位为基准，因此只要偶数位不越界即可
             * 3.使用双层循环代替单层循环，去除对偶数位的重复判断
             */
            int prime = 1, even = 0; // 定义奇数指针和偶数指针
            while (even < A.length - 1) {
                if ((A[even] & 1) != 0) { // 偶数位为非法元素
                    while ((A[prime] & 1) != 0) { // 循环找到奇数位中的非法元素
                        prime += 2;
                    }
                    // 交换非法元素
                    int temp = A[prime];
                    A[prime] = A[even];
                    A[even] = temp;
                }
                even += 2;
            }
            return A;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}
